using System;

namespace LeetCode {
    public class LPS {
        public string LongestPalindrome (string s) {
            char[] chars = s.ToCharArray ();
            int length = chars.Length;
            bool[, ] lps = new bool[length, length];
            int maxlen = 1;
            int start = 0;
            for (int i = 0; i < length; i++) {
                for (int j = 0; j <= i; j++) {
                    if (i - j < 2) {
                        lps[j, i] = chars[i] == chars[j];
                    } else {
                        lps[j, i] = lps[j + 1, i - 1] && (chars[i] == chars[j]);
                    }
                    if (lps[j, i] && (i - j + 1) > maxlen) {
                        maxlen = i - j + 1;
                        start = j;
                    }
                }
            }
            return s.Substring (start, maxlen);
        }
        public string LongestPalindromes (string s) {
            int n = s.Length;
            bool[, ] dp = new bool[n, n];
            string result = "";
            for (int j = n - 1; j >= 0; j--) {
                for (int i = j; i < n; i++) {
                    if (i == j) {
                        dp[j, i] = true;
                    } else if (i == j + 1) {
                        dp[j, i] = s[j] == s[i];
                    } else {
                        dp[j, i] = dp[j + 1, i - 1] && (s[j] == s[i]);
                    }
                    if (dp[j, i] && i + 1 - j > result.Length) {
                        result = s.Substring (j, i + 1 - j);
                    }
                }
            }
            return result;
        }
        public string LongestPalindrome1 (string s) {
            int n = s.Length;
            string res = "";
            bool[] p = new bool[n];
            for (int j = n - 1; j >= 0; j--) {
                for (int i = n - 1; i >= j; i--) {
                    if (i == j) {
                        p[i] = true;
                    } else if (i == j + 1) {
                        p[i] = s[j] == s[i];
                    } else {
                        p[i] = p[i - 1] && s[j] == s[i];
                    }

                    if (p[i] && i - j + 1 > res.Length) {
                        res = s.Substring (j, i + 1 - j);
                    }
                }
            }
            return res;
        }
    }
}